package com.xk._03真题骗._05动态规划;

/*
 * @description: https://leetcode.cn/problems/longest-palindromic-substring/
 * @author: xu
 * @date: 2022/11/3 15:08
 */
public class _5最长回文子串 {
    /**
     * 动态规划--二维数组
     * dp[i][j] 表示 s[i,j] 是否为回文子串 存储 true OR false
     * @param s
     * @return
     */
    public String longestPalindrome1(String s) {
        if (s == null || s.length() == 0) return s;
        char[] chars = s.toCharArray();
        int length = chars.length;
        boolean[][] dp = new boolean[length][length];
        // maxLen：最长回文子串的长度
        // begin：最长回文子串的开始索引
        int begin = 0, maxLen = 1;
        // 从下到上（i由大到小）
        for (int i  = length - 1; i >= 0; i--) {
            // 从左到右（j由小到大）
            for (int j = i; j < length; j++) {
                int len = j - i + 1;
                dp[i][j] = (chars[i] == chars[j]) && (len <= 2 || dp[i+1][j-1]);
                if (dp[i][j] && len > maxLen) { // 说明chars[i,j] 是回文子串
                    maxLen = len;
                    begin = i;
                }
            }
        }
        return new String(chars, begin, maxLen);
    }

    /**
     * 动态规划--一维数组
     * @param s
     * @return
     */
    public String longestPalindrome2(String s) {
        if (s == null || s.length() == 0) return s;
        char[] chars = s.toCharArray();
        int length = chars.length;
        boolean[] dp = new boolean[length];
        // maxLen：最长回文子串的长度
        // begin：最长回文子串的开始索引
        int begin = 0, maxLen = 1;
        // 从下到上（i由大到小）
        for (int i  = length - 1; i >= 0; i--) {
            // 从右到左（j由大到小）（为了方便使用上次一维数组中的前面的内容）
            for (int j = length - 1; j >= i; j--) {
                int len = j - i + 1;
                dp[j] = (chars[i] == chars[j]) && (len <= 2 || dp[j-1]);
                if (dp[j] && len > maxLen) { // 说明chars[i,j] 是回文子串
                    maxLen = len;
                    begin = i;
                }
            }
        }
        return new String(chars, begin, maxLen);
    }

    /*
     * 拓展中心法1
     * 假设字符串("abbaba")的长度为n，那么一共有 n + (n-1) = 2n - 1 个扩展中心
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     */
    public String longestPalindrome11(String s) {
        if (s == null || s.length() <= 1) return s;
        char[] chars = s.toCharArray();
        // maxLen：最长回文子串的长度
        // begin：最长回文子串的开始索引
        int begin = 0, maxLen = 1;
        for (int i = chars.length - 2; i >= 1; i--) {
            // 以字符为中心向左右扩展
            int len1 = palindromeLength(chars, i-1, i+1);
            // 以字符右边的间隙为中心向左右扩展
            int len2 = palindromeLength(chars, i, i+1);
            len1 = Math.max(len1, len2);
            if (maxLen < len1){
                maxLen = len1;
                begin = i - ((maxLen - 1) >> 1);
            }
        }
        // 以0索引位置的字符右边的间隙为扩展中心的最长回文子串长度是2
        if (chars[0] == chars[1] && 2 > maxLen) {
            maxLen = 2;
            begin = 0;
        }
        return new String(chars, begin, maxLen);
    }
    /*
     * return 从left开始向左扫描，从right开始向右扫描，获得的最长回文子串的长度
     */
    private int palindromeLength(char[] chars, int left, int right) {
        while (left >= 0 && right < chars.length && chars[left] == chars[right]){
            left--;
            right++;
        }
        return right - left - 1;
    }

    /*
     * 拓展中心法2 优化
     * 算法的核心思想：由连续的相同字符组成的子串作为扩展中心
     * 所以，字符串 "babbbabaa" 的扩展中心有 "b" "a" "bbb" "a" "b" "aa"
     */
    public String longestPalindrome12(String s) {
        if (s == null || s.length() <= 1) return s;
        char[] chars = s.toCharArray();
        // maxLen：最长回文子串的长度
        // begin：最长回文子串的开始索引
        int begin = 0, maxLen = 1;
        int i = 0;
        while (i < chars.length) {
            // 找到右边第一个不等于chars[i]的位置
            int r = i;
            int l = i - 1;
            while (++r < chars.length && chars[r] == chars[i]);
            // r会成为新的i
            i = r;
            // 向左向右扩展
            while (l >= 0 && r < chars.length && chars[l] == chars[r]) {
                l--;
                r++;
            }
            // 扩展结束 chars[l+1, r-1] 就是刚才找到的最大回文子串
            // ++l 后，l就是刚才找到的最大回文子串的开始索引
            int len = r - ++l; // r - l - 1 = r - (l + 1) = r - ++l
            if (len > maxLen) {
                maxLen = len;
                begin = l;
            }
        }
        return new String(chars, begin, maxLen);
    }

    /*
     * Manacher(马拉车法)
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) return s;
        char[] chars = s.toCharArray();
        // maxLen：最长回文子串的长度
        // begin：最长回文子串的开始索引
        int idx = 0, maxLen = 1;
        // 预处理
        char[] cs = preprocessor(chars);
        // 构建m数组
        int[] m = new int[cs.length];
        int c = 1, r = 1, lastIdx = cs.length - 2;
        for (int i = 2; i < lastIdx; i++) {
            if (i < r) {
                int li = (c << 1) - i;
                m[i] = i + m[li] <= r ? m[li] : r - i;
            }
            // 以i为中心 向两边进行扩展
            while (cs[i + m[i] + 1] == cs[i - m[i] - 1]){
                m[i] += 1;
            }
            // 更新c、r
            if (i + m[i] > r) {
                c = i;
                r = i + m[i];
            }
            // 找出更大的回文子串
            if (m[i] > maxLen) {
                maxLen = m[i];
                idx = i;
            }
        }
        int begin = (idx - maxLen) >> 1;
        return new String(chars, begin, maxLen);
    }
    private char[] preprocessor(char[] oldChars) {
        char[] chars = new char[(oldChars.length << 1) + 3];
        chars[0] = '^';
        chars[1] = '#';
        chars[chars.length - 1] = '$';
        for (int i = 0; i < oldChars.length; i++) {
            int index = (i + 1) << 1;
            chars[index] = oldChars[i];
            chars[index + 1] = '#';
        }
        return chars;
    }

    public static void main(String[] args) {
        String s = new _5最长回文子串().longestPalindrome("abba");
        System.out.println(s);
    }
}
